// @algorithm @lc id=100338 lang=cpp
// @title gou-jian-cheng-ji-shu-zu-lcof

#include "algm/algm.h"
#include <iostream>
#include <string>
#include <vector>
using namespace std;
class Solution {
    // @test([1, 2, 3, 4, 5])=[120,60,40,30,24]
public:
    vector<int> constructArr(vector<int> &a) {
        int n = a.size();
        if (n == 0) {
            return {};
        }
        vector<int> left(n, 0);
        vector<int> right(n, 0);
        vector<int> ans(n, 0);
        left[0] = 1;
        for (int i = 1; i < n; ++i) {
            left[i] = left[i - 1] * a[i - 1];
        }
        right[n - 1] = 1;
        for (int i = n - 2; i >= 0; --i) {
            right[i] = right[i + 1] * a[i + 1];
        }
        for (int i = 0; i < n; ++i) {
            ans[i] = left[i] * right[i];
        }
        return ans;
    }
};